package com.github.tangmonkmeat;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/7/30 上午9:27
 */
public class 树的子结构 {

    public static void main(String[] args) {

        try {
            int a = 1 / 0;
            System.out.println(1);
        }catch (Exception e){
            System.out.println(2);
        }finally {
            System.out.println(3);
        }

        System.out.println(4);

        //TreeNode root = new TreeNode(4);
        //TreeNode node1 = new TreeNode(5);
        //TreeNode node2 = new TreeNode(2);
        //TreeNode node4 = new TreeNode(3);
        //
        //root.left = node1;
        ////root.right = node2;
        //node1.left = node4;
        //
        //
        //TreeNode root1 = new TreeNode(4);
        //TreeNode node11 = new TreeNode(5);
        //TreeNode node21 = new TreeNode(2);
        //
        //root1.left = node11;
        //root1.right = node21;
        //
        //boolean subStructure = isSubStructure(root, root1);
        //
        //System.out.println(subStructure);

    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null){
            return false;
        }
        List<Integer> a = new ArrayList<>();
        List<Integer> b = new ArrayList<>();

        bst(A,a);
        bst(B,b);

        Object[] a1 = a.toArray();
        Object[] b1 = b.toArray();

        int i = 0;
        for(int j = 0;i < b1.length && j < a1.length;){
            if(b1[i] == a1[j]){
                int lj = 2 * j + 1, rj = 2 * j + 2;
                int li = 2 * i + 1, ri = 2 * i + 2;
                if(lj < b1.length && li < a1.length && b1[li] == a1[lj]){
                }else{
                    j++;
                    continue;
                }

                if(rj < b1.length && ri < a1.length && b1[ri] == a1[rj]){
                    j = rj + 1;
                    i = ri + 1;
                }else{
                    i = (li - 1) / 2;
                    j = lj + 1;
                    continue;
                }
            }
            j++;
        }

        return i >= b1.length - 1;
    }

    public static void bst(TreeNode node, List<Integer> res){
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(node);

        while(!queue.isEmpty()){
            int len = queue.size();
            for(int i = 0;i < len;i++){
                TreeNode pop = queue.pop();
                if(pop != null) {
                    res.add(pop.val);
                    queue.add(pop.left);
                    queue.add(pop.right);
                }
            }
        }
    }
    
    static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

}
